#include "HeapSort.h"
#include "my_lib.h"


void
Heap_sort__sift_down(int * array, int start, int end)
{
	int parent = start,
	    child,
	    swap;

	while (parent * 2 + 1 <= end) {
		child = parent * 2 + 1;
		swap = parent;

		if (array[swap] < array[child])
			swap = child;

		if (child+1 <= end && array[swap] < array[child+1])
			swap = child+1;

		if (swap != parent) {
			swap_ints(&array[parent], &array[swap]);
			parent = swap;
		} else {
			return;
		}
	}
}



void
Heap_sort__sift_up(int * array, int start, int end)
{
	int child = end,
	    parent = (end - 1) / 2;

	/*
	 * 'start' is a kind of left barrier for this function
	 */
        while (child > start) {
		if (array[(child - 1) / 2] < array[child]) {
			swap_ints(&array[parent], &array[child]);

			child  = parent--;
			parent /= 2;
		} else
			return;
	}
}



void
Heap_sort__heapify(int* array, int size)
{
	int start = size / 2 - 1;

	while (start >= 0) {
		Heap_sort__sift_down(array, start--, size - 1);
	}
}



void
Heap_sort(int *array, int size)
{
	int end = size - 1;

	Heap_sort__heapify(array, size);

	while (end > 0) {
		swap_ints(&array[end], &array[0]);

		Heap_sort__sift_down(array, 0, --end);
	}
}
